package 动态规划;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-05
 */
public class 最小编辑代价 {
    static int min = Integer.MAX_VALUE;
    static int add = 1, delete = 2, edit = 3;
    static boolean[] viseted;

    /**
     * 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，
     * 分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
     */
    public static void main(String[] args) {
        long a = System.currentTimeMillis();
        System.out.println(minEditCost("abcaefaf", "fdafa", 1, 2, 3));
        long b = System.currentTimeMillis();
        System.out.println(b - a);
        viseted = new boolean[3];
        long c = System.currentTimeMillis();
        minEdit("abcaefaf", "fdafa", 0, 0, 0);
        System.out.println(min);
        System.out.println(System.currentTimeMillis() - c);


    }


    private static void minEdit(String source, String target, int curEditNum, int sourceIndex, int targetIndex) {
        // 剪枝：当前操作数已不可能打破记录
        if (curEditNum >= min) return;

        // 处理剩余字符（必须放在剪枝之后）
        if (sourceIndex >= source.length() || targetIndex >= target.length()) {
            int remainingOps = 0;
            if (sourceIndex < source.length()) {
                remainingOps += (source.length() - sourceIndex) * delete;
            } else if (targetIndex < target.length()) {
                remainingOps += (target.length() - targetIndex) * add;
            }
            min = Math.min(curEditNum + remainingOps, min);
            return;
        }

        // 正常匹配逻辑
        if (source.charAt(sourceIndex) == target.charAt(targetIndex)) {
            minEdit(source, target, curEditNum, sourceIndex + 1, targetIndex + 1);
        } else {
            // 删除操作
            minEdit(source, target, curEditNum + delete, sourceIndex + 1, targetIndex);
            // 新增操作
            minEdit(source, target, curEditNum + add, sourceIndex, targetIndex + 1);
            // 替换操作
            minEdit(source, target, curEditNum + edit, sourceIndex + 1, targetIndex + 1);
        }
    }

    public static int minEditCost(String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.length() + 1, n = str2.length() + 1;
        char[] char1 = str1.toCharArray(), char2 = str2.toCharArray();
        int[][] dp = new int[m][n];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + dc;
        for (int i = 1; i < n; i++) dp[0][i] = dp[0][i - 1] + ic;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (char1[i - 1] == char2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + dc, dp[i][j - 1] + ic), dp[i - 1][j - 1] + rc);
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
